import java.util.Arrays;

public class Solution324 {
    public void wiggleSort(int[] nums) {
        int[] f=new int[5001];
        for (int num : nums) {
            f[num]++;
        }
        int l=0,r=5000;
        for (int i=0;i<nums.length;i++){
            if (i%2==0){
                while (f[l]==0){
                    l++;
                }
                nums[i]=l;
                f[l]--;
            }else{
                while (f[r]==0){
                    r--;
                }
                nums[i]=r;
                f[r]--;
            }
        }
        l=0;
        r=nums.length%2==0?nums.length-2:nums.length-1;
        while (l<r){
            int t=nums[l];
            nums[l]=nums[r];
            nums[r]=t;
            l+=2;
            r-=2;
        }
    }

    public static void main(String[] args) {
        int[] nums=new int[]{1,5,1,1,6,4};
        new Solution324().wiggleSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
